package day1_array.leetcode.sliding_window;

/**
 * @Author: yuisama
 * @Date: 2022/9/8 12:55
 * @Description:滑动窗口之字符串的子串问题 LeetCode567
 *
 */
public class Num567_CheckInclusion {
    public boolean checkInclusion(String s1, String s2) {
        // 需求字符哈希表
        int[] needs = new int[26];
        // 窗口字符哈希表
        int[] windows = new int[26];
        // 需求字符哈希表键值对个数
        int needsSize = 0;
        int left = 0,right = 0;
        // 窗口中有效字符键值对
        int valid = 0;
        // 初始化需求字符哈希表
        for (int i = 0; i < s1.length(); i++) {
            char c = s1.charAt(i);
            needs[c - 'a'] ++;
            if (needs[c - 'a'] == 1) {
                needsSize ++;
            }
        }
        // 扫描s2
        while (right < s2.length()) {
            // 向后滑动窗口
            char c = s2.charAt(right);
            right ++;
            // 更新窗口信息
            if (needs[c - 'a'] > 0) {
                // 先更新
                windows[c - 'a'] ++;
                if (windows[c - 'a'] == needs[c - 'a']) {
                    valid ++;
                }
            }
            // 判断是否需要滑动窗口左侧，此时窗口字符个数超过s1.length就需要滑动左侧
            // 这里是固定窗口大小，因此用if和while是一样的
            while (right - left >= s1.length()) {
                if (valid == needsSize) {
                    // 找到了有效子串
                    return true;
                }
                char d = s2.charAt(left);
                left ++;
                // 更新窗口
                if (needs[d - 'a'] > 0) {
                    // 先判断
                    if (windows[d - 'a'] == needs[d - 'a']) {
                        valid --;
                    }
                    windows[d - 'a'] --;
                }
            }
        }
        // 扫描完还没找到解
        return false;
    }
}
